UVA1189 题解

题目链接

给定一个正整数 $n$，求它的一个倍数 $m$ 使得 $m$ 只含有数字 $0$ 和 $1$。

我们可以 $1$ 开始进行 $\operatorname{dfs}$，设当前搜索到的数为 $k$，则下一次从 $10k$ 和 $10k+1$ 进行搜索，搜到 $n$ 的倍数直接退出。

题目说 $m$ 不超过 $100$ 位，为了避免写高精度，我们可以把当前搜索到的数模 $n$ 的余数传入 $\operatorname{dfs}$，而把搜索到的数作为字符串，每次在末尾添上 $0/1$，同时记录数字的位数，位数到达 $100$ 停止搜索。

为了加快效率，我们可以加一个剪枝，搜索到一个可行解后停止搜索。

实测效率还是比较快的，代码也很简短，应该很容易理解。

Code

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int n, flag;

void dfs(string s, int cnt, int mod) {
    if (cnt >= 100 || flag) return;
    if (mod == 0) {
        flag = 1;
        cout << s << endl;
        return;
    }
    dfs(s + '0', cnt + 1, mod * 10 % n);
    dfs(s + '1', cnt + 1, (mod * 10 + 1) % n);
}

int main() {
    while (~scanf("%d", &n) && n) {
        flag = 0;
        dfs("1", 1, 1);
    }
    return 0;
}